The present invention relates to an apparatus for estimating motion and a method thereof, and more particularly, to an apparatus for estimating real-time motion in a motion-compensated predictive coder for data compression of motion image data and a method thereof.
During transmission of or recording on a recording medium of motion image data, a predictive coding technique is utilized to increase data compression efficiency. Especially in data having a great amount of motion, a motion-compensated predictive coding technique is generally employed to prevent the degradation of data compression efficiency which occurs when using a simple predictive coding in which only an error signal is transmitted or recorded. In motion-compensated predictive coding, motion information is also extracted to thereby transmit and record both the error signal and motion information.
In the motion-compensated predictive coding, the block most similar to a certain block of a current frame is searched for in a fixed search area of a previous frame, and the searched block is used as a predicted value during the predictive coding. The search area is constituted by all the surrounding areas centering around the certain block of the current frame, and the relative distance from the current position to the position of the similar block of the previous frame within the search area is termed as a "motion vector" or "displacement vector." That is, the motion vector is the relative distance of the current block position and the position of the most similar previous block. Thus, an absolute value of the motion vector becomes large when the motion is great, becomes small when the motion is slight, and becomes (0, 0) when there is no motion. This search of the motion vector of the previous block having a minimum error value is called motion estimation, and is generally accomplished by a block-matching algorithm (BMA).
The BMA commonly utilizes a full search technique wherein the most similar previous block is obtained by a comparative operation in the ratio of 1:1 with the current block, with respect to all blocks formable in the search area. However, because all blocks are compared one-to-one in the full search, the resulting overflow of the comparative operation and the need for many I/O pins impede the hardware realization of a real-time motion vector estimator.
The similarity of the compared blocks is calculated by using a minimum absolute error D(i, j), which can be written as: ##EQU1## where a(m, n) designates a current pixel value, b(m+j, n+j) is a previous pixel value, and (i, j) is a motion vector value.
Among the D(i, j) values, the relative position of the previous block having the minimum error value with respect to the current block becomes the motion vector. The following characteristics exemplify the operation amount and processing speed required for realizing the hardware for real-time motion estimation:
data rate: 13.5 MHz PA1 current block size: 256 pixels (16.times.16) PA1 motion vector range: -8.ltoreq.i, j.ltoreq.7 PA1 search window size: 961 pixels (31.times.31) PA1 previous block size: 256 pixels (16.times.16) PA1 number of the previous block: 256 PA1 previous block formation means for simultaneously inputting first and second serial pixel data strings within the search window, and sequentially outputting in parallel the serial pixel data strings corresponding to the respective previous pixel blocks; PA1 block-matching algorithm processing means for sequentially inputting the serial pixel data strings, outputted from the previous block formation means, and a third serial pixel data string of the current pixel block to simultaneously perform one-to-one comparison of the plurality of previous pixel blocks with the current pixel block in parallel, thereby outputting in parallel the respective absolute error data strings of the plurality of previous blocks with respect to the current pixel block; PA1 minimum absolute error detecting means for inputting and dividing the parallel absolute error data strings into a plurality of groups, obtaining minimum absolute error data of each group, and comparing the minimum absolute error data of the groups to one another, thereby producing a minimum absolute error data within the search window; PA1 motion vector generating means for generating a motion vector corresponding to the minimum absolute error data produced in the search window, by being synchronized to the operation of the minimum absolute error detecting means for obtaining the minimum value; and PA1 output controlling means for outputting the absolute error data of a motion vector (0, 0), the produced minimum absolute error data, and the generated motion vector to an I/O bus, and selectively outputting the absolute error data among a plurality of absolute error data strings corresponding an external motion vector input via the I/O bus.
Here, the total operating number of the full search technique is 256.times.256 for each block, and 256 operations are required for each pixel. Since a subtraction operation, absolute value calculation and accumulation must be performed for each operation, real-time processing requires 256 operations for each pixel period, which requires approximately 0.29 ns per data. Therefore, it can be appreciated that, when the processing is carried out per data, real-time processing is difficult due to the relation between the required total number of operations and the processing speed.